USACO07MAR黄金阵容均衡

发表于
  • Description
    有$N(1\le N\le 10^5)$天，$M(1\le M\le 30)$种能力值。每一天可能有几种能力值+1。一段时期内若每种能力值都增加相同的量则称为均衡的，求最长的均衡时期。
  • Solution
    • 记个前缀和，方便快速询问。
    • 我的思路就此打止了，我真是太弱了
    • 如果第 $a+1$ 天到第$b$天这段时期是均衡的，那么有 $ \forall_{i=1}^{M} day[b][i]-day[a][i] = k (k为常数) $
    • 接着又可以发现，记 $s[i][j] = day[i][j]-day[i][1]$ ，那么有$\forall_{i=1}^{M}s[b][i] = s[a][i]$
    • 找这些相同的东西统计答案就行了，可以先用字典序先排一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar(), bool f = 0 ){
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) if (c == '-') f = 1 ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    if (f) x = -x ;
}
const int maxn = 1e5+5, maxm = 35 ;
int n, m, a[maxn][maxm] ;
struct node {
    int id, t[maxm] ;
    friend bool operator < ( node a, node b ) {
        for ( int i = 1 ; i <= m ; i ++ )
            if ( a.t[i] != b.t[i] ) return a.t[i] < b.t[i] ;
    }
    void init() {
        for ( int i = m ; i ; i -- )
            t[i] -= t[1] ;
    }
    friend bool operator == ( node a, node b ) {
        for ( int i = 1 ; i <= m ; i ++ )
            if (a.t[i] != b.t[i]) return false ;
        return true ;
    }
} s[maxn] ;
int main() {
#ifndef ONLINE_JUGDE
    freopen ( "P1360.in", "r", stdin ) ;
    freopen ( "P1360.out", "w", stdout ) ;
#endif
    int i, j, k, x ;
    int ans = 0, l = n, r = 0 ; 
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(x) ;
        for ( j = 1 ; j <= m ; j ++, x >>= 1 ) a[i][j] = x&1 ;
        bool fg = 1 ;
        for ( j = 2 ; j <= m ; j ++ )
            if ( a[i][j] != a[i][j-1] ) fg = 0 ;
        if (fg) ans = 1 ;
    }
    for ( i = 1 ; i <= n ; i ++ )
        for ( j = 1 ; j <= m ; j ++ )
            s[i].t[j] = s[i - 1].t[j] + a[i][j] ;
    for ( i = 1 ; i <= n ; i ++ ) s[i].init(), s[i].id = i ;
    sort(s, s+n+1) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        if (s[i] == s[i -1]) {
            l = min(l, s[i].id) ;
            r = max(r, s[i].id) ;
            ans = max(r-l, ans) ;
        } else {
            l = s[i].id ;
            r = s[i].id ;
        }
    }
    printf ( "%d\n", ans ) ;
    return 0 ;
}